FPL may be equivalent to FO but not equivalent to PFP

摘要

Given a class of finite models we would like to expand each model (allowingnew elements but the old universe is a separate sort), making the expressivepower of LFP (least fix point logic) and PFP (inductive logic) similar whilenot changing the expressive power of FO (first order logic). This continues inmath.LO/9411235.